Increasingly in real-time systems, computer processors must handle the self-suspension of tasks and determine the feasibility of these task sets. Self-suspensions can result both due to hardware and software architecture. At the hardware level, the addition of multi-core processors, dedicated cards and various input/output (I/O) devices, such as external memory drives, can necessitate task self-suspensions. Furthermore, the software that utilizes these hardware systems can employ synchronization points and other algorithmic techniques that also result in self-suspensions. Thus, a schedulability test that does not significantly overestimate the temporal resources needed to execute self-suspending task sets would be of benefit to these modern computing systems.
Unfortunately the problem is NP-Hard, as can be shown through an analysis of the interaction of self-suspensions and task deadlines. In practice, the relaxation of a deadline in a self-suspending task set may result in temporal infeasibility. Many uniprocessor, priority-based scheduling algorithms introduce scheduling anomalies since they do not account for this interaction. The most straightforward, correct approach for testing the schedulability of these task sets is to treat self-suspensions as task costs; however, this can result in significant under-utilization of the processor if the duration of self-suspensions is large relative to task costs.
A number of different approaches have been proposed to test the schedulability of self-suspending task sets. The dominant strategy is to upperbound the duration of self-suspensions that needs to be treated as task cost. One approach, testing preemptive task sets with multiple self-suspensions per task under Global Earliest Deadline First (GEDF) on multiple processor systems, has shown significant improvement over the prior art. An earlier test computes the maximum utilization factor for tasks with single self-suspensions scheduled under Earliest Deadline First (EDF) for uniprocessor systems. The test works by analyzing priorities to determine the number of tasks that may be executed during a self-suspension. Other approaches test schedulability by analyzing the worst case response time of tasks due to external blocking events.
The design of scheduling policies for self-suspending task sets also remains a challenge. While EDF has desirable properties for many real-time uniprocessor scheduling problems, certain anomalies arise when scheduling task sets with both self-suspensions and hard deadlines. In some instances, it is possible to schedule a task set under EDF with tight deadlines, while the same task set with looser deadlines fails. Finding an anomaly-free scheduling priority for self-suspending task sets remains an open problem. Accordingly, a schedulability test that determines the feasibility of hard, non-preemptive, self-suspending task sets with multiple self-suspensions for each task is needed.